{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rotate Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxRotateFunction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #旋转函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>假设&nbsp;<code>arr<sub>k</sub></code>&nbsp;是数组&nbsp;<code>nums</code>&nbsp;顺时针旋转 <code>k</code> 个位置后的数组，我们定义&nbsp;<code>nums</code>&nbsp;的 <strong>旋转函数</strong>&nbsp;&nbsp;<code>F</code>&nbsp;为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>F(k) = 0 * arr<sub>k</sub>[0] + 1 * arr<sub>k</sub>[1] + ... + (n - 1) * arr<sub>k</sub>[n - 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回&nbsp;<em><code>F(0), F(1), ..., F(n-1)</code>中的最大值&nbsp;</em>。</p>\n",
    "\n",
    "<p>生成的测试用例让答案符合&nbsp;<strong>32 位</strong> 整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [4,3,2,6]\n",
    "<strong>输出:</strong> 26\n",
    "<strong>解释:</strong>\n",
    "F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25\n",
    "F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16\n",
    "F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23\n",
    "F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26\n",
    "所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [100]\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-100 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rotate-function](https://leetcode.cn/problems/rotate-function/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rotate-function](https://leetcode.cn/problems/rotate-function/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,6]', '[100]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            res+=i*x\n",
    "        t=sum(nums)\n",
    "        cnt=res\n",
    "        while nums:\n",
    "            cnt=cnt+t-n*nums.pop()\n",
    "            res=max(res,cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        tot = sum(nums)\n",
    "        F = 0\n",
    "        for i in range(len(nums)):\n",
    "            F += nums[i] * i\n",
    "        print(F)\n",
    "        ans = F\n",
    "        for i in range(len(nums)-1):\n",
    "            prev = F\n",
    "            F = prev - nums[len(nums)-i-1]*(len(nums)-1)+tot - nums[len(nums)-i-1]\n",
    "            ans = max(ans,F)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        allsum = sum(nums)\n",
    "        prev = sum(i * nums[i] for i in range(len(nums)))\n",
    "        ans = prev\n",
    "        leng = len(nums)\n",
    "        for _ in range(leng):\n",
    "            latest = nums.pop()\n",
    "            prev = prev - (leng - 1) * latest + (allsum - latest)\n",
    "            ans = max(prev, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "        # F(k + 1) = F(k) + sum(nums) - n * nums[-k]\n",
    "        n, total, f = len(nums), sum(nums), sum(i * num for i, num in enumerate(nums))\n",
    "        res = f\n",
    "        for i in range(1, n):\n",
    "            f += total - n * nums[-i]\n",
    "            res = max(res, f)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        num_sum = sum(nums)\n",
    "        num_size = len(nums)\n",
    "        if num_size == 0:\n",
    "            return 0\n",
    "        for i in range(num_size):\n",
    "            res += i * nums[i]\n",
    "        result_save = res\n",
    "        for i in range(num_size-1, 0, -1):\n",
    "            temp_res = num_sum - num_size*nums[i]\n",
    "            result_save+=temp_res\n",
    "            res = max(res, result_save)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n,s = len(nums),sum(nums)\n",
    "        ans = a = sum(i*nums[i] for i in range(n))\n",
    "        for num in nums[:-1]:\n",
    "            a += n*num-s\n",
    "            if a>ans: ans = a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        total = sum(nums)\n",
    "\n",
    "        # 初始化\n",
    "        pre = ans = sum(nums[i] * i for i in range(n)) \n",
    "        # 移动窗口\n",
    "        for i in range(1, n):\n",
    "            pre = pre - (total - nums[i - 1]) + (n - 1) * nums[(n - 1 + i) % n]\n",
    "            ans = ans if ans > pre else pre\n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        res = float('-inf')\n",
    "        s = sum(nums)\n",
    "        F = 0\n",
    "        for i, ele in enumerate(nums):\n",
    "            F += i*ele\n",
    "        res = max(res, F)\n",
    "        nums = nums[:] + nums[:]\n",
    "        for i in range(1, len(nums)//2):\n",
    "            F = F - s + len(nums)//2 * nums[i-1]\n",
    "            res = max(res, F)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n_len = len(nums)\n",
    "        if n_len == 1:\n",
    "            return 0\n",
    "        tol = sum(nums)\n",
    "        # 计算f[0]的结果\n",
    "        f = 0\n",
    "        for i in range(n_len):\n",
    "            f += i * nums[i]\n",
    "        # 每一次旋转都是减去(n-1)f(x) + tol - sum的结果\n",
    "        res = f\n",
    "        for i in range(n_len - 1, 0, -1):\n",
    "            f = f - n_len * nums[i] + tol\n",
    "            res = max(res, f)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        # 数学，相邻F的差是可以很快计算出来的\n",
    "        '''\n",
    "        nums = [4,3,2,6]\n",
    "        F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16\n",
    "        F(0) = (3 * 6) + (0 * 4) + (1 * 3) + (2 * 2) = 0 + 3 + 4 + 18 = 25\n",
    "        F1 - F0 = sum(nums) - 4*6\n",
    "        每次的差就是sum - n*nums[-(i+1)]\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += i*nums[i]\n",
    "        print(res)\n",
    "        crt = res\n",
    "        for i in range(n):\n",
    "            crt = crt + s - n*nums[-(i+1)]\n",
    "            print(crt)\n",
    "            res = max(res,crt)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        sumi, sums = 0, 0\n",
    "        for i, v in enumerate(nums):\n",
    "            sumi += i * v\n",
    "            sums += v\n",
    "\n",
    "        maxs, ns = sumi, len(nums)\n",
    "        sum0 = 0\n",
    "        for i in range(1, ns):\n",
    "            sum0 += nums[i - 1]\n",
    "            sumk = sumi + (ns - 0) * sum0 - sums * i\n",
    "            if sumk > maxs:\n",
    "                maxs = sumk\n",
    "        return maxs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        f0 = 0\n",
    "        nsum = sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            f0 += i * nums[i]\n",
    "        msum = f0\n",
    "\n",
    "        i = 0\n",
    "        last = len(nums) - 1\n",
    "        # F(0)+numSum−n×nums[n−1]\n",
    "        fi = f0\n",
    "        while i < len(nums):\n",
    "            fi = fi + nsum - len(nums) * nums[last]\n",
    "            msum = max(msum, fi)\n",
    "            last -= 1\n",
    "            i += 1\n",
    "        return msum\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        f, n = 0, len(nums)\n",
    "        sums = sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            f += i * nums[i]\n",
    "        ans = f\n",
    "        for i in range(1, n):\n",
    "            f = f + sums - n * nums[n - i]\n",
    "            ans = max(ans, f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        f = 0\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            f += i*nums[i]\n",
    "        maxf = f\n",
    "        ss = sum(nums)\n",
    "        for i in range(length-1,-1,-1):\n",
    "            f = f - (length-1)*nums[i] + ss - nums[i]\n",
    "            maxf = max(f,maxf)\n",
    "        return maxf\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        t: int = 0\n",
    "        s :int = 0\n",
    "        for j in range(len(nums)):\n",
    "            t = t + nums[j] * j\n",
    "            s += nums[j]\n",
    "        ans = t\n",
    "        # s = sum(nums)\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "\n",
    "            n = t+s-len(nums)*nums[len(nums)-i]\n",
    "                \n",
    "            ans = max(ans, n)\n",
    "            t = n\n",
    "            \n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        sum_val = sum(nums)\n",
    "        max_val = 0\n",
    "        total = 0\n",
    "        for i in range(len(nums)):\n",
    "            total += nums[i] * i\n",
    "        max_val = total\n",
    "        pre_val = total\n",
    "        for i in range(1, len(nums)):\n",
    "            total = pre_val + sum_val - len(nums) * nums[len(nums) - i]\n",
    "            max_val = max(total, max_val)\n",
    "            pre_val = total\n",
    "        return max_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=F=sum(i*num for i,num in enumerate(nums))\n",
    "        sum_nums=sum(nums)\n",
    "        for i in range(n-1,0,-1):\n",
    "            F+=sum_nums-n*nums[i]\n",
    "            if F>ans:ans=F\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n, m = len(nums), sum(nums)\n",
    "        q = v = sum(i*nums[i] for i in range(n))\n",
    "        for i in range(1, n):\n",
    "            q += m - n*nums[n-i]\n",
    "            if q > v: v = q\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "#         mx = 0\n",
    "#         f0 = sum([i*j for i,j in zip(nums,[k for k in range(len(nums))])])\n",
    "#         f = [f0]\n",
    "#         sums = sum(nums)\n",
    "#         for i in range(1,len(nums)):\n",
    "#             f.append(f[i-1]-sums+len(nums)*nums[i-1])\n",
    "#         return max(f)\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        # F(k + 1) = F(k) + sum(nums) - n * nums[-k]\n",
    "        n, s, f = len(nums), sum(nums), sum(i * num for i, num in enumerate(nums))\n",
    "        ans = f\n",
    "        for i in range(1, n):\n",
    "            f += s - n * nums[-i]\n",
    "            ans = max(ans, f)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, A: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        F(k): A 顺时针旋转 k 个位置后的数组\n",
    "        F(k) = 0 * A[0] + 1 * A[1] + ... + (n - 1) * A[n - 1]\n",
    "        求 F(0), F(1), ..., F(n-1)中的最大值\n",
    "\n",
    "        [4,3,2,6]\n",
    "        idx = [0,1,2,3]\n",
    "        F(0) = idx*[4,3,2,6] = 25\n",
    "        F(1) = idx*[6,4,3,2] = 16 = 25 + sum([4,3,2]) - 6*3\n",
    "        F(2) = idx*[2,6,4,3] = 23 = 16 + sum([6,4,3]) - 2*3\n",
    "        F(3) = idx*[3,2,6,4] = 26 = 23 + sum([2,6,4]) - 3*3\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        res = pre = sum(i*x for i,x in enumerate(A))\n",
    "        s = sum(A[:-1])\n",
    "\n",
    "        for i in range(n-1, 0, -1):\n",
    "            pre = pre + s - A[i]*(n-1)\n",
    "            res = max(pre, res)\n",
    "            s = s + A[i] - A[i-1]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        # f = a = sum([i*j for i,j in zip(nums,[k for k in range(len(nums))])])\n",
    "        f = a = sum(i * num for i, num in enumerate(nums))\n",
    "        sums = sum(nums)\n",
    "        for i in range(1,len(nums)):\n",
    "            a = a-sums+len(nums)*nums[i-1]\n",
    "            f = a if a>f else f\n",
    "        return f\n",
    "# class Solution:\n",
    "#     def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "#         # F(k + 1) = F(k) + sum(nums) - n * nums[-k]\n",
    "#         n, s, f = len(nums), sum(nums), sum(i * num for i, num in enumerate(nums))\n",
    "#         ans = f\n",
    "#         for i in range(1, n):\n",
    "#             f += s - n * nums[-i]\n",
    "#             ans = max(ans, f)\n",
    "#         return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        add_nums=[]\n",
    "        length=len(nums)\n",
    "        all_num=sum(nums)\n",
    "        base_nums=0\n",
    "        for i in range(length-1,0,-1):\n",
    "            base_nums+=i*nums[i]\n",
    "            add_nums.append(all_num-length*nums[i])\n",
    "        max_n=base_nums\n",
    "        cur=base_nums\n",
    "        for num in add_nums:\n",
    "            cur=cur+num\n",
    "            if cur>max_n:\n",
    "                max_n=cur\n",
    "        return max_n\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        f,n,sumNums = 0,len(nums),sum(nums)\n",
    "        for i in range(n):\n",
    "            f += i*nums[i]\n",
    "        res = f\n",
    "        for i in range(n-1,-1,-1):\n",
    "            f = f + sumNums - n*nums[i]\n",
    "            res = max(res,f)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        # 16:31~16:46 简单递推,复杂度O(n)\n",
    "        n = len(nums)\n",
    "        raw_sum, cur_sum, max_sum = 0, 0, 0\n",
    "        for i in range(n):\n",
    "            raw_sum += nums[i]\n",
    "            cur_sum += i * nums[i]\n",
    "        max_sum = cur_sum\n",
    "        for i in range(n-1):\n",
    "            cur_sum += raw_sum - n*nums[n-1-i]\n",
    "            max_sum = max(max_sum, cur_sum)\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        f, n, numSum = 0, len(nums), sum(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            f += i * num\n",
    "        res = f\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            f = f + numSum - n * nums[i]\n",
    "            res = max(res, f)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        # cv = sum([i * j for i, j in enumerate(nums)])\n",
    "        cv = 0\n",
    "        for i, j in enumerate(nums):\n",
    "            cv += i * j\n",
    "        mv = cv\n",
    "        for i in range(1, n):\n",
    "            cv += s - n * nums[n - i]\n",
    "            if cv > mv:\n",
    "                mv = cv\n",
    "        return mv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += i * nums[i]\n",
    "        s = sum(nums)\n",
    "        curr = res\n",
    "        for k in range(1, n):\n",
    "            curr += s - n * nums[n - k]\n",
    "            res = max(res, curr)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        #错位相减\n",
    "        s=sum(nums)\n",
    "        f=0\n",
    "        for i in range (len(nums)):\n",
    "           f+=i*nums[i]\n",
    "        #保存此刻的f值\n",
    "        cur=f\n",
    "        loction=len(nums)-1\n",
    "        while loction!=-1:\n",
    "          cur+=s-len(nums)*nums[loction]\n",
    "          f=max(f,cur)\n",
    "          loction-=1\n",
    "        return f\n",
    "        #s=1*4+1*3+1*2+1*6\n",
    "        #f=0*4+1*3+2*2+3*6\n",
    "        #f+s=1*4+2*3+3*2+4*6\n",
    "        #f=f+s-4*6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        total = F = 0\n",
    "        n, ans = len(nums), -float('inf')\n",
    "        for i in range(n):\n",
    "            total += nums[i]\n",
    "            F += i * nums[i]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans = max(F, ans)\n",
    "            F = F - n * nums[i] + total\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        win_v=0\n",
    "        l=0\n",
    "        r=n-2\n",
    "        s=0\n",
    "        win_v=sum(nums[l:r+1])\n",
    "        for i in range(1,n):\n",
    "            s+=i*nums[i]\n",
    "\n",
    "        ans=s\n",
    "        for i in range(1,n):\n",
    "\n",
    "            s+=win_v-nums[-i]*(n-1)\n",
    "            ans=max(ans,s)\n",
    "\n",
    "            win_v-=nums[r]\n",
    "            l=((l-1)+n)%n\n",
    "            r=((r-1)+n)%n\n",
    "            win_v+=nums[l]\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(i,now,res):\n",
    "        #     nonlocal ans\n",
    "        #     if i==n:\n",
    "        #         ans=max(ans,res)\n",
    "        #         return\n",
    "        #     dfs(i+1,(now+1)%n,res+nums[i]*now)\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     dfs(0,i,0)\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "        # f=[0]*n\n",
    "        # for i in range(n):\n",
    "        #     f[i]=nums[0]*i\n",
    "        # for i in range(1,n):\n",
    "        #     temp=f[-1]\n",
    "        #     for j in range(n-1,0,-1):\n",
    "        #         f[j]=f[j-1]+nums[i]*(j)\n",
    "        #     f[0]=temp\n",
    "        # return max(f)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        s=sum(nums)\n",
    "        cur_result=0\n",
    "        for i in range(len(nums)):\n",
    "            cur_result+=i*nums[i]\n",
    "        max_result=cur_result\n",
    "        for n in nums:\n",
    "            cur_result+=n*len(nums)-s\n",
    "            if cur_result>max_result:\n",
    "                max_result=cur_result\n",
    "        return max_result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        f, n, numSum = 0, len(nums), sum(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            f += i * num\n",
    "        res = f\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            f = f + numSum - n * nums[i]\n",
    "            res = max(res, f)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n>0:\n",
    "            curr_sum = 0\n",
    "            num_sum = 0\n",
    "            for i in range(n):\n",
    "                curr_sum += i * nums[i]\n",
    "                num_sum += nums[i]\n",
    "            \n",
    "            max_sum = curr_sum\n",
    "            for i in range(1,n):\n",
    "                curr_sum = curr_sum + num_sum - n * nums[-i]\n",
    "                if curr_sum > max_sum:\n",
    "                    max_sum = curr_sum\n",
    "        \n",
    "        return max_sum\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<=1:\n",
    "            return 0\n",
    "        now=0\n",
    "        s=sum(nums)\n",
    "        \n",
    "        for i in range(n):\n",
    "            now+=i*nums[i]\n",
    "        ans=now \n",
    "        for i in range(1,n):\n",
    "            #print(now)\n",
    "            now=now+s-n*nums[-i]\n",
    "            #print(now)\n",
    "            ans=max(ans,now)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        f = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            f += i * nums[i]\n",
    "        \n",
    "        numSum = sum(nums)\n",
    "        res = f\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            f = f + numSum - n * nums[i]\n",
    "            res = max(res, f)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        cur = sum(i * x for i, x in enumerate(nums))\n",
    "        print(f'cur={cur}')\n",
    "        ans = cur\n",
    "        for i in range(1, n):\n",
    "            last = nums[n - i]\n",
    "            t = cur + s - last \n",
    "            t -= (n - 1) * last \n",
    "            cur = t\n",
    "            ans = max(ans, cur)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        s1=sum(nums[1:])\n",
    "        s2=0\n",
    "        for i in range(1,len(nums)):\n",
    "            s2=s2+i*nums[i]\n",
    "        ss=s2\n",
    "        for i in range(1,len(nums)):\n",
    "            s2=s2-s1+(len(nums)-1)*nums[i-1]\n",
    "            s1 = s1 - nums[i] + nums[i - 1]\n",
    "            if s2>ss:ss=s2\n",
    "        return ss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        all_sum = 0\n",
    "        first = 0\n",
    "        for i in range(len(nums)):\n",
    "            all_sum+=nums[i]\n",
    "            first+=i*nums[i]\n",
    "        ret = first\n",
    "        nums = nums[::-1]\n",
    "        for i in range(len(nums)):\n",
    "            first = first+all_sum-len(nums)*nums[i]\n",
    "            if first>ret:\n",
    "                ret=first\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n, tot = len(nums), sum(nums)\n",
    "        f = [0] * n\n",
    "\n",
    "        for i, v in enumerate(nums):\n",
    "            f[0] += i * v\n",
    "\n",
    "        ans = f[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] - (tot - nums[i - 1]) + (n - 1) * nums[i - 1]\n",
    "            ans = max(ans, f[i])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        total = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        for index, item in enumerate(nums):\n",
    "            total += item * index\n",
    "        \n",
    "        res = total\n",
    "        index = 1\n",
    "        while index < len(nums):\n",
    "            total = total - (s - nums[index - 1]) + (nums[index - 1] * (n - 1))\n",
    "            print(total)\n",
    "            res = max(res, total)\n",
    "            index += 1\n",
    "            # 0 1 2 3 4\n",
    "            # 4 0 1 2 3\n",
    "            # 3 4 0 1 2\n",
    "            # 2 3 4 0 1\n",
    "            # 1 2 3 4 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = sum([i * nums[i] for i in range(n)])\n",
    "        numSum = sum(nums)\n",
    "        max_f = f\n",
    "        for i in range(1, n):\n",
    "            new_f = f + numSum - n*nums[n-i]\n",
    "            max_f = max(max_f, new_f)\n",
    "            f = new_f\n",
    "        return max_f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        numSum = sum(nums)\n",
    "        ret = f = sum([i * n for i, n in enumerate(nums)])\n",
    "        for i in range(1, len(nums)):\n",
    "            f = f + numSum - nums[-1 * i] * len(nums)\n",
    "            if f > ret: ret = f\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        j = n \n",
    "        s = sum(nums)\n",
    "        \n",
    "        while j > 0:\n",
    "            dp[0] += nums[n - j] * (n - j)\n",
    "            j -= 1\n",
    "        ans = dp[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i- 1] - s + n * nums[i - 1]\n",
    "            ans = max(ans, dp[i])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        j = n \n",
    "        s = sum(nums)\n",
    "        \n",
    "        while j > 0:\n",
    "            dp[0] += nums[n - j] * (n - j)\n",
    "            j -= 1\n",
    "        ans = dp[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i- 1] - s + n * nums[i - 1]\n",
    "            ans = max(ans, dp[i])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        F = sum(idx*n for idx, n in enumerate(nums))\n",
    "        ret = F\n",
    "        for i in nums[1:][::-1]:\n",
    "            F = -len(nums) * i + s + F\n",
    "            ret = max(ret, F)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        F(0)=0×nums[0]+1×nums[1]+…+(n−1)×nums[n−1]]\n",
    "        F(1)=1×nums[0]+2×nums[1]+…+0×nums[n−1]=F(0)+numSum−n×nums[n−1]\n",
    "        F(k)=F(k−1)+numSum−n×nums[n−k]\n",
    "        \"\"\"\n",
    "        f, n, numSum = 0, len(nums), sum(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            f += i * num\n",
    "        res = f\n",
    "        # 从倒数第一个元素到第二个元素遍历\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            f = f + numSum - n * nums[i]\n",
    "            res = max(res, f)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        ans = 0\n",
    "        for i in range(n) :\n",
    "            ans += i * nums[i]\n",
    "        count = ans\n",
    "        for i in range(n-1, 0, -1) :\n",
    "            tmp = count + s - n * nums[i]\n",
    "            ans = max(ans, tmp)\n",
    "            count = tmp\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25\n",
    "        F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16\n",
    "        F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23\n",
    "        F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26\n",
    "\n",
    "        f1 - f0 = [4 + 3 + 2 + 6] - 4 * 6\n",
    "        f2 - f1 = [6 + 4 + 3 + 2] - 4 * 2\n",
    "        f3 - f2 = [2 + 6 + 4 + 3] - 4 * 2\n",
    "\n",
    "        f(i) = f(i - 1) + numSum - n * num[i]\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        f = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            f += i * nums[i]\n",
    "        \n",
    "        numSum = sum(nums)\n",
    "        res = f\n",
    "        for i in range(n):\n",
    "            f = f + numSum - n * nums[n - i - 1]\n",
    "            res = max(res, f)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # 计算数组总和\n",
    "        sum = 0\n",
    "        f = 0  # f(0)的值\n",
    "        for i in range(n):\n",
    "            sum += nums[i]\n",
    "            f += i * nums[i]\n",
    "\n",
    "        # 动态规划-优化后\n",
    "        max_f = f \n",
    "        # 旋转一次\n",
    "        for i in range(n):\n",
    "            temp = f + sum - n * nums[(n - i - 1)]\n",
    "            max_f = max(max_f, temp)\n",
    "            f = temp\n",
    "        return max_f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\r\n",
    "        S,N=sum(nums),len(nums)\r\n",
    "        f=sum(i*nums[i] for i in range(N))\r\n",
    "        ret=f\r\n",
    "        for i in range(1,N):\r\n",
    "            f=f+S-N*nums[N-i]\r\n",
    "            ret=max(ret,f)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        f = sum([i*nums[i] for i in range(n)])\n",
    "        fmax = f\n",
    "        for i in range(1, n):\n",
    "            f = f + s - n * nums[-i]\n",
    "            fmax = max(f,fmax)\n",
    "        return fmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        t: int = 0\n",
    "        s :int = 0\n",
    "        k: int = 0\n",
    "        for j in range(len(nums)):\n",
    "            t = t + nums[s] * k\n",
    "            s = (s+1)%len(nums)\n",
    "            k += 1\n",
    "        ans.append(t)\n",
    "\n",
    "        s = sum(nums)\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "                \n",
    "            ans.append(t+s-len(nums)*nums[len(nums)-i])\n",
    "            t = ans[-1]\n",
    "            \n",
    "            \n",
    "        return max(ans)\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        F = [0] * N\n",
    "        F[0] = sum([i * nums[i] for i in range(N)])\n",
    "        S = sum(nums)\n",
    "        for i in range(1, N):\n",
    "            F[i] = F[i - 1] + (S - N * nums[N - i])\n",
    "        # print(F)\n",
    "        return max(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        t: int = 0\n",
    "        s :int = 0\n",
    "        k: int = 0\n",
    "        for j in range(len(nums)):\n",
    "            t = t + nums[s] * k\n",
    "            s = (s+1)%len(nums)\n",
    "            k += 1\n",
    "        ans.append(t)\n",
    "\n",
    "        s = sum(nums)\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "                \n",
    "            ans.append(t+s-len(nums)*nums[len(nums)-i])\n",
    "            t = ans[-1]\n",
    "            \n",
    "            \n",
    "        return max(ans)\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        total_sum = sum(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = sum([i * num for i, num in enumerate(nums)])\n",
    "        res = dp[0]\n",
    "        for i in range(1, n):\n",
    "            a = total_sum - nums[n - i] * (n)\n",
    "            dp[i] = dp[i - 1] + a\n",
    "            res = max(dp[i], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        ans = -float(\"inf\")\n",
    "        n = len(nums)\n",
    "        total = sum([i * nums[i] for i in range(n)])\n",
    "        d = sum(nums)\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            total += d\n",
    "            total -= n * nums[-i]\n",
    "            ans = max(total, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        f_list = []\n",
    "        sum_nums = sum(nums)\n",
    "        nums_length = len(nums)\n",
    "        f_one = 0\n",
    "        for idx in range(len(nums)):\n",
    "            f_one += idx * nums[idx]\n",
    "        f_list.append(f_one)\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx == 0:\n",
    "                continue\n",
    "            f_list.append(f_list[idx - 1] + sum_nums - nums_length * nums[nums_length - idx])\n",
    "        print(f_list)\n",
    "        return max(f_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        sums=sum(nums)\n",
    "        F=[0]*n\n",
    "        F[0]=sum([i*nums[i] for i in range(n)])\n",
    "        for i in range(1,n):\n",
    "            F[i]=F[i-1]+sums-n*nums[n-i]\n",
    "        return max(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        def lt396(nums):\n",
    "            n=len(nums)\n",
    "            sum_=sum(nums)\n",
    "            max_=sum([i*e for i,e in enumerate(nums)])\n",
    "            temp=max_\n",
    "            for i in range(1,n):\n",
    "                head=n-i\n",
    "                temp=temp-nums[head]*(n-1)+(sum_-nums[head])\n",
    "                max_=max(max_,temp)\n",
    "            return max_\n",
    "        return lt396(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "        ssum = 0\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        for i in range(n):\n",
    "            ssum += i * nums[i]\n",
    "            if i >= 1:\n",
    "                pre+= nums[i]\n",
    "\n",
    "        nums = nums + nums.copy()\n",
    "        \n",
    "\n",
    "        left = 1\n",
    "        right = n\n",
    "\n",
    "        pre_sum = ssum\n",
    "\n",
    "        while right < 2*n:\n",
    "            # print(pre_sum)\n",
    "            # print(pre)\n",
    "            pre_sum = pre_sum - pre + (n-1) * nums[right]\n",
    "\n",
    "            pre = pre - nums[left] + nums[right]\n",
    "\n",
    "            ssum = max(pre_sum, ssum)\n",
    "\n",
    "            right += 1\n",
    "            left += 1\n",
    "        \n",
    "        return ssum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        \n",
    "        temp=sum([i*nums[i] for i in range(len(nums))])\n",
    "        ans=temp\n",
    "        #list1=[temp]\n",
    "        zz=sum(nums)\n",
    "        for i in range(1,len(nums)):\n",
    "            now=temp+zz-len(nums)*nums[len(nums)-i]\n",
    "            temp=now\n",
    "            #list1.append(now)\n",
    "            ans=max(ans,now)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        sumnums=sum(nums)\n",
    "        f=sum([x*nums[x] for x in range(n)])\n",
    "        res=f\n",
    "        for i in range(1,n):\n",
    "            f=f-sumnums+n*nums[i-1]\n",
    "            res=max( res, f )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        allSum, n = sum(nums), len(nums)\n",
    "        prev = sum([i * nums[i] for i in range(n)])\n",
    "        ans = prev\n",
    "        for i in range(1, len(nums)):\n",
    "            j = n - i\n",
    "            fi = prev + allSum - n * nums[j]\n",
    "            ans = max(ans, fi)\n",
    "            prev = fi\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        #找规律\n",
    "        deta=sum(nums)\n",
    "        pre=sum([nums[i]*i for i in range(len(nums))])\n",
    "        #枚举右移次数\n",
    "        ans,n=pre,len(nums)\n",
    "        for i in range(1,n):\n",
    "            cur=pre+deta-n*nums[-i]\n",
    "            ans=max(ans,cur)\n",
    "            pre=cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        total = sum(nums)\n",
    "        cur_val = sum([i*nums[i] for i in range(n)])\n",
    "        result = cur_val\n",
    "        for i in range(1,n):\n",
    "            # print(cur_val, total, nums[n-i])\n",
    "            cur_val += total - n*nums[n-i]\n",
    "            result = max(result, cur_val)\n",
    "            # 25 - 3*6 + 9\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        # k = 0\n",
    "        # 0 * arr[0] + 1 * arr[1] + 2 * arr[2] + 3 * arr[3]\n",
    "        # k = 1\n",
    "        # 0 * arr_1[0] + 1 * arr_1[1] + 2 * arr_1[2] + 3 * arr_1[3] =\n",
    "        # 0 * arr[3] + 1 * arr[0] + 2 * arr[1] + 3 * arr[2]\n",
    "        # F[0] + \n",
    "        # k = 2\n",
    "        # 0 * arr[2] + 1 * arr[3] + 2 * arr[0] + 3 * arr[1]\n",
    "\n",
    "        # F[1] - F[0] = arr[0] +  arr[1] + arr[2] - 3 * arr[3] + 0 * arr[3]\n",
    "        #             = numSums - 4 * arr[3]\n",
    "        # F[1] = F[0] + numSums - 4 * arr[3] \n",
    "\n",
    "        # F[2] - F[1] = arr[3] + arr[0] + arr[1] - 3 * arr[2] + 0 * arr[3]\n",
    "        # F[2] - F[0] = 2 * arr[0] + 2 * arr[1] - 2 * arr[2] - 2 * arr[3] \n",
    "        # F[2] = F[1] + numSums - 4 * arr[2]\n",
    "        # F[k] = F[k - 1] + numSums - n * arr[n - k]\n",
    "\n",
    "        n = len(nums)\n",
    "        numSums = sum(nums)\n",
    "        F = []\n",
    "        f0 = sum([i * nums[i] for i in range(n)])\n",
    "        F.append(f0)\n",
    "        for i in range(1, n):\n",
    "            F.append(F[-1] + numSums - n * nums[n - i])\n",
    "        return max(F)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/rotate-function/description/comments/1521151\n",
    "    # 向右旋转一次：当前结果+sum(nums) - n*当前最后一位\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = nums.__len__()\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        sm, f = 0, [0]*n\n",
    "        for i in range(n):\n",
    "            sm += nums[i]\n",
    "            f[0] += i*nums[i]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i-1] + sm - n*nums[n-i]\n",
    "        return max(f) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        # F(0) = nums[0]*0 + nums[1]*1 + nums[2]*2 + ... + nums[n-1]*(n-1)\n",
    "        # F(1) = nums[0]*1 + nums[1]*2 + nums[2]*3 + ... + nums[n-1]*0\n",
    "        # F(1) - F(0) = nums[0] + nums[1] + ... + nums[n-2] - (n-1)*nums[n-1]\n",
    "        #             = total(nums) - n*nums[n-1]\n",
    "        # F(k) - F(k-1) = total(nums) - n*nums[n-k]\n",
    "        n = len(nums)\n",
    "        total = sum(nums)\n",
    "        F = [0] * n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            F[0] += i*nums[i]\n",
    "            res = max(res,F[0])\n",
    "        for i in range(1,n):\n",
    "            F[i] = total + F[i-1] - n * nums[n-i]\n",
    "            res = max(F[i],res)\n",
    "        # print(F)\n",
    "        return max(F)\n",
    "    def maxRotateFunction1(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        matrix = [ [0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                matrix[i][j] = i*nums[j]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            x = 0\n",
    "            y = i\n",
    "            total = 0\n",
    "            while x < n:\n",
    "                total += matrix[x][y%n]\n",
    "                x += 1\n",
    "                y += 1\n",
    "            res = max(res,total)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        dp=[0]*len(nums)\n",
    "        coeff=[]\n",
    "        for i in range(len(nums)):\n",
    "            dp[0]+=i*nums[i]\n",
    "        _sum=sum(nums)\n",
    "        res=dp[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i]=dp[i-1]+_sum-len(nums)*nums[len(nums)-i]\n",
    "            res=max(res,dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m=0\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        count = 0\n",
    "        dp = [0]*n\n",
    "        k = sum(nums)\n",
    "        for i in range(n):\n",
    "            count += m*nums[i]\n",
    "            m+=1\n",
    "        dp[0] = count\n",
    "        for j in range(1,n):\n",
    "            dp[j] = dp[j-1]-k+nums[j-1]*n\n",
    "        \n",
    "\n",
    "        return max(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n>0:\n",
    "            all_sum = [0]*n\n",
    "            num_sum = 0\n",
    "            for i in range(n):\n",
    "                all_sum[0] += i * nums[i]\n",
    "                num_sum += nums[i]\n",
    "            \n",
    "            max_sum = all_sum[0]\n",
    "            for i in range(1,n):\n",
    "                all_sum[i] = all_sum[i-1] + num_sum - n * nums[-i]\n",
    "                if all_sum[i] > max_sum:\n",
    "                    max_sum = all_sum[i]\n",
    "        \n",
    "        return max_sum\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        # Brute Force TOE O(n^2)\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        ans = -10**8\n",
    "        for offset in range(0, -n, -1):\n",
    "            tmp = 0\n",
    "            for i in range(n):\n",
    "                tmp += nums[offset + i]*i\n",
    "            if tmp > ans:\n",
    "                ans = tmp\n",
    "        return ans\n",
    "        '''\n",
    "        # F3 = F2 + sum - 4*A1\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        sumup = sum(nums)\n",
    "        for i in range(n):\n",
    "            dp[0] += nums[i]*i\n",
    "        for i in range(-1, -n, -1):\n",
    "            dp[i] = dp[i + 1] + sumup - n*nums[i]\n",
    "        return max(dp)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "\n",
    "        sums = sum(nums)\n",
    "        lens = len(nums)\n",
    "        \n",
    "        # f(1) - f(0) = (1-0)*4 + (2-1)*3 + (3-2)*3 + (0-3)*6 \n",
    "        # f(2) - f(1) = (2-1)*4 + (3-2)*3 + (0-3)*3 + (1-0)*6 \n",
    "        # f(n) - f(n-1) = (n-(n-1)))*4 + ((n+1)-n)*3 + (0-3)*3 + (1-0)*6 \n",
    "        #               = sum(nums) - nums[lens-n] * lens\n",
    "        \n",
    "        f = [0] * (len(nums))\n",
    "        for i in range(len(nums)) :\n",
    "            f[0] += nums[i] * i \n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            f[i] = sums - nums[lens-i] * lens + f[i-1]\n",
    "\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        F = [0]*n\n",
    "        summ = 0\n",
    "        for i in range(n):\n",
    "            F[0] += nums[i]*i\n",
    "            summ += nums[i]\n",
    "        maxi = F[0]\n",
    "        for j in range(1, n):\n",
    "            F[j] = F[j-1] + summ - n * nums[(n-j)%n]\n",
    "            if F[j] > maxi:\n",
    "                maxi = F[j]\n",
    "        return maxi\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        # if len(nums) == 1:\n",
    "            # return nums[0]\n",
    "\n",
    "        #k:  k, k+1, ..., n - 1, 0 , ... k - 1\n",
    "        #k + 1, k+2, ...   0, 1,           k\n",
    "        # F(k + 1) - F(k) = 1, 1, (-n + 1), 1\n",
    "        # index + k = n - 1\n",
    "        # index = n - k - 1\n",
    "        # F(k + 1) - F(k) = numSum - n * num[n - k - 1], k = 0, n-2\n",
    "        numSum = 0\n",
    "        f = [0] * len(nums)\n",
    "        for idx, n in enumerate(nums):\n",
    "            f[0] += idx * n\n",
    "            numSum += n\n",
    "        maxSum = f[0]\n",
    "        for i in range(len(nums) - 1):\n",
    "            print(i)\n",
    "            f[i + 1] = f[i] + numSum - len(nums) * nums[len(nums) - i - 1]\n",
    "            if f[i + 1] >= maxSum:\n",
    "                maxSum = f[i + 1]\n",
    "        \n",
    "        return maxSum\n",
    "        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        num_sum = sum(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = sum([i * nums[i] for i in range(n)])\n",
    "        for i in range(1, n):\n",
    "            # print('---nums---', nums)\n",
    "            # dp[i] = dp[i - 1] + sum(nums[:-1]) - (n - 1) * nums[-1]\n",
    "            # dp[i] = dp[i - 1] + num_sum - n * nums[-1]\n",
    "            dp[i] = dp[i - 1] + num_sum - n * nums[n-i]\n",
    "            # temp = nums.pop()\n",
    "            # nums.insert(0, temp)\n",
    "        # print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        arr_len=len(nums)\n",
    "        res=cur=sum(list(map(lambda x,y:x*y,nums,[i for i in range(arr_len)])))\n",
    "        count=1\n",
    "        arr_sum=sum(nums)\n",
    "        while count<arr_len:\n",
    "            cur=cur+arr_sum-arr_len*nums[arr_len-count]\n",
    "            res=max(res,cur)\n",
    "            count+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        f = [0] * n\n",
    "        f[0] = sum(i * nums[i] for i in range(n))\n",
    "        ans = f[0]\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1] + n * nums[(i - 1) % n] - s\n",
    "            ans = max(ans, f[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        if l==1:\n",
    "            return 0\n",
    "        qzh=[0]*(l+1)\n",
    "        f=[0]*(l+1)\n",
    "        for i in range(l):\n",
    "            qzh[i+1]=qzh[i]+nums[i]*i\n",
    "            f[i+1]=f[i]+nums[i]\n",
    "        ori=qzh[-1]\n",
    "        for i in range(1,l):\n",
    "            res=qzh[-1]-qzh[-i]-(l-i)*(f[-1]-f[-i])\n",
    "            ori=max(ori,qzh[l-i]+i*f[l-i]+res)\n",
    "        return ori\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxRotateFunction(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        num_sum = sum(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = sum([i * nums[i] for i in range(n)])\n",
    "        for i in range(1, n):\n",
    "            # 每次只用加上整个数组的和, 再减去数组最后一个元素*(n-1), 再减数组最后一个元素\n",
    "            # print('---nums---', nums)\n",
    "            # dp[i] = dp[i - 1] + sum(nums[:-1]) - (n - 1) * nums[-1]\n",
    "            # dp[i] = dp[i - 1] + num_sum - n * nums[-1]\n",
    "            dp[i] = dp[i - 1] + num_sum - n * nums[n-i]\n",
    "            # temp = nums.pop()\n",
    "            # nums.insert(0, temp)\n",
    "        # print(dp)\n",
    "        return max(dp)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
